#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
    寻找数组中每个元素的下一个更大（更小）元素
    单调栈保存以遍历的元素的下标
    入栈元素的下标 可以O(1)的时间复杂度直接找到该元素 
    入的是元素的话，需要O(n)的空间记录元素的下标 or O(n)的时间复杂度去找到小标

    求下一个更大的元素时， 小的元素（下标）入栈，构造单调递减的栈（栈底到栈顶递减），
    while{找到比栈顶大的元素后栈顶元素弹出，当前更大元素（下标）继续与栈顶元素比较，
    没有找到比栈顶更大的元素(直到栈为空或者栈顶元素大于当前更大元素，当前更大元素入栈)}
    没有找到更大元素，小的元素（下标）入栈

    求下一个更小的元素时， 大的元素（下标）入栈，构造单调递增的栈（栈底到栈顶递增），
    while{找到比栈顶小的元素后栈顶元素弹出，更小元素（下标）继续与栈顶元素比较，
    没有找到比栈顶更小的元素(直到栈为空或者栈顶元素小于当前更小元素，当前更小元素入栈)}
    没有找到更小元素，大的元素（下标）入栈



*/

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int getIndex(int nums1, int* nums2, int nums2Size)
{
    for (int i = 0; i < nums2Size; i++)
    {
        if (nums1 == nums2[i])
        {
            return i;
        }
    }
    return -1;
}
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    *returnSize = nums1Size;
    int *ret = (int *)malloc(sizeof(int) * (*returnSize));
    memset(ret, -1, sizeof(int) * (*returnSize));
    int *monotonic_stack = (int *)malloc(sizeof(int) * nums1Size);
    int top = -1;
    for (int i = 0; i < nums1Size; i++)
    {
        memset(monotonic_stack, 0, sizeof(int) * nums1Size);
        top = -1;
        int exit_flag = 0;
        for (int j = getIndex(nums1[i], nums2, nums2Size); j < nums2Size; j++)
        {
            // 只需和栈底元素作比较就好了
            while (top >= 0 && nums2[j] > nums2[monotonic_stack[0]])
            {
                // ret下标按nums1的顺序来的
                ret[i] = nums2[j];
                monotonic_stack[top--];
                exit_flag = 1;// 找到一个下一个更大元素就好了
            }
            monotonic_stack[++top] = j;
            if (exit_flag) 
                break;
                
        }
    }
    return ret;
}
